Search Results

Documents authored by Kawamura, Akitoshi

Document
DOI: 10.4230/LIPIcs.STACS.2022.32
Online Scheduling on Identical Machines with a Metric State Space

Authors: Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, and Hanna Sumita

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
This paper introduces an online scheduling problem on m identical machines with a metric state space, which generalizes the classical online scheduling problem on identical machines, the online traveling salesman problem, and the online dial-a-ride problem. Each job is associated with a source state, a destination state, a processing time, and a release time. Each machine can process a job on and after its release time. Before processing a job, a machine needs to change its state to the source state (in a time corresponding to the distance), and after the process of the job, the machine’s state becomes the destination state. While related research deals with a model in which only release times are unknown to the algorithm, this paper focuses on a general model in which destination states and processing times are also unknown. The main result of this paper is to propose a O(log m/log log m)-competitive online algorithm for the problem, which is best possible. A key approach is to divide the difficulty of the problem. To cope with unknown release times, we provide frameworks to produce a min{2ρ+1/2, ρ+2}-competitive algorithm using a ρ-competitive algorithm for a basic case where all jobs are released at time 0. Then, focusing on unknown destination states and processing times, we construct an O(log m/log log m)-competitive algorithm for the basic case. We also provide improved algorithms for some special cases.
Cite as

Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, and Hanna Sumita. Online Scheduling on Identical Machines with a Metric State Space. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goko_et_al:LIPIcs.STACS.2022.32,
  author =	{Goko, Hiromichi and Kawamura, Akitoshi and Kawase, Yasushi and Makino, Kazuhisa and Sumita, Hanna},
  title =	{{Online Scheduling on Identical Machines with a Metric State Space}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.32},
  URN =		{urn:nbn:de:0030-drops-158421},
  doi =		{10.4230/LIPIcs.STACS.2022.32},
  annote =	{Keywords: Online scheduling, Competitive analysis, Online dial-a-ride}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.30
Average-Case Polynomial-Time Computability of Hamiltonian Dynamics

Authors: Akitoshi Kawamura, Holger Thies, and Martin Ziegler

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We apply average-case complexity theory to physical problems modeled by continuous-time dynamical systems. The computational complexity when simulating such systems for a bounded time-frame mainly stems from trajectories coming close to complex singularities of the system. We show that if for most initial values the trajectories do not come close to singularities the simulation can be done in polynomial time on average. For Hamiltonian systems we relate this to the volume of "almost singularities" in phase space and give some general criteria to show that a Hamiltonian system can be simulated efficiently on average. As an application we show that the planar circular-restricted three-body problem is average-case polynomial-time computable.
Cite as

Akitoshi Kawamura, Holger Thies, and Martin Ziegler. Average-Case Polynomial-Time Computability of Hamiltonian Dynamics. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kawamura_et_al:LIPIcs.MFCS.2018.30,
  author =	{Kawamura, Akitoshi and Thies, Holger and Ziegler, Martin},
  title =	{{Average-Case Polynomial-Time Computability of Hamiltonian Dynamics}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.30},
  URN =		{urn:nbn:de:0030-drops-96125},
  doi =		{10.4230/LIPIcs.MFCS.2018.30},
  annote =	{Keywords: Computable Analysis, Real computation, Dynamical systems, Average-case complexity, Computation in physics}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2017.23
Polynomial Running Times for Polynomial-Time Oracle Machines

Authors: Akitoshi Kawamura and Florian Steinberg

Published in: LIPIcs, Volume 84, 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017)

Abstract
This paper introduces a more restrictive notion of feasibility of functionals on Baire space than the established one from second-order complexity theory. Thereby making it possible to consider functions on the natural numbers as running times of oracle Turing machines and avoiding second-order polynomials, which are notoriously difficult to handle. Furthermore, all machines that witness this stronger kind of feasibility can be clocked and the different traditions of treating partial functionals from computable analysis and second-order complexity theory are equated in a precise sense. The new notion is named "strong polynomial-time computability", and proven to be a strictly stronger requirement than polynomial-time computability. It is proven that within the framework for complexity of operators from analysis introduced by Kawamura and Cook the classes of strongly polynomial-time computable functionals and polynomial-time computable functionals coincide.
Cite as

Akitoshi Kawamura and Florian Steinberg. Polynomial Running Times for Polynomial-Time Oracle Machines. In 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 84, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kawamura_et_al:LIPIcs.FSCD.2017.23,
  author =	{Kawamura, Akitoshi and Steinberg, Florian},
  title =	{{Polynomial Running Times for Polynomial-Time Oracle Machines}},
  booktitle =	{2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-047-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{84},
  editor =	{Miller, Dale},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2017.23},
  URN =		{urn:nbn:de:0030-drops-77370},
  doi =		{10.4230/LIPIcs.FSCD.2017.23},
  annote =	{Keywords: second-order complexity, oracle Turing machine, computable analysis, second-order polynomial, computational complexity of partial functionals}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.46
A Lower Bound on Opaque Sets

Authors: Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, and János Pach

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.
Cite as

Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, and János Pach. A Lower Bound on Opaque Sets. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 46:1-46:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kawamura_et_al:LIPIcs.SoCG.2016.46,
  author =	{Kawamura, Akitoshi and Moriyama, Sonoko and Otachi, Yota and Pach, J\'{a}nos},
  title =	{{A Lower Bound on Opaque Sets}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{46:1--46:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.46},
  URN =		{urn:nbn:de:0030-drops-59386},
  doi =		{10.4230/LIPIcs.SoCG.2016.46},
  annote =	{Keywords: barriers; Cauchy-Crofton formula; lower bound; opaque sets}
}
Document
DOI: 10.4230/DagRep.5.9.77
Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392)

Authors: Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly

Published in: Dagstuhl Reports, Volume 5, Issue 9 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15392 "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis." It includes abstracts on most talks presented during the seminar, a list of open problems that were discussed and partially solved during the meeting as well as a bibliography on the seminar topic that we compiled during the seminar.
Cite as

Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly. Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392). In Dagstuhl Reports, Volume 5, Issue 9, pp. 77-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.5.9.77,
  author =	{Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno},
  title =	{{Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392)}},
  pages =	{77--104},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{9},
  editor =	{Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.9.77},
  URN =		{urn:nbn:de:0030-drops-56861},
  doi =		{10.4230/DagRep.5.9.77},
  annote =	{Keywords: Computability and complexity in analysis, computations on real numbers, reducibilities, descriptive complexity, computational complexity, reverse and constructive mathematics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact